package com.ln.prac.base.m202206.d15;

import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * <pre>
 *
 * </pre>
 *
 * @Author zhangj
 * @Date 2022/6/15 23:03
 */
public class SortTest {

    /**
     * 快速排序1
     */
    public static List<Integer> fastSort1(List<Integer> list) {
        // 递归终止
        if(list.size() <= 1) {
            return list;
        }

        int num = list.get(0);

        List<Integer> left = list.stream().filter(x -> x < num).collect(Collectors.toList());
        List<Integer> mid = list.stream().filter(x -> x == num).collect(Collectors.toList());
        List<Integer> right = list.stream().filter(x -> x > num).collect(Collectors.toList());

        // 递归
        left = fastSort1(left);
        right = fastSort1(right);

        // 合并
        left.addAll(mid);
        left.addAll(right);

        return left;
    }


    public static void fastSort2(Integer[] A) {
        fastSort2(A, 0, A.length);
    }

    public static void fastSort2(Integer[] A, int l, int r) {
        // 递归终止
        if(r - l <= 1) {
            return;
        }

        // 整理数组并返回中间的下标
        int i = partition(A, l, r);

        // 递归
        fastSort2(A, l, i);
        fastSort2(A, i + 1, r);

        // 合并
        merge(A, l, i, r);
    }

    private static void merge(Integer[] a, int l, int mid, int r) {
        // 设置哨兵
        Integer[] b = Arrays.copyOfRange(a, l, mid + 1);
        Integer[] c = Arrays.copyOfRange(a, mid, r + 1);
        b[b.length - 1] = c[c.length - 1] = Integer.MAX_VALUE;
        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if(b[i] < c[j]) {
                a[k] = b[i++];
            } else {
                a[k] = c[j++];
            }
        }
    }

    private static int partition(Integer[] a, int l, int r) {
        int x = a[l];
        int i = l + 1, j = r;
        while (i != j) {
            if(a[i] < x){
                ++i;
            } else {
              swap(a, i, --j);
            }
        }
        swap(a, i -1, l);
        return i - 1;
    }

    private static void swap(Integer[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    /**
     * 插入
     */
    public static void insertSort(Integer[] a) {
        for (int i = 1; i < a.length; i++) {
            int j = i;
            int tmp = a[i];
            for (; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(Integer[] a) {
        for (int i = a.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if(a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }


    public static void main(String[] args) {
        Integer[] A = new Integer[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            A[i] = random.nextInt(100);
        }

//        List<Integer> sortList = fastSort1(Arrays.asList(A));
//        System.out.println(sortList);


//        fastSort2(A);
//        System.out.println(Arrays.asList(A));

//        insertSort(A);
//        System.out.println(Arrays.asList(A));

        bubbleSort(A);
        System.out.println(Arrays.asList(A));

    }
}
